package com.lwl.Algorithmic_data_structure.class18暴力递归2动态规划;

/**
 * @author lwl
 * @Description 给一个一维数组长度n(从1开始)，一个起始点start，一个终点aim，以及步数k；请你求出刚好k步到aim的方法数
 * @date 2023/6/6 21:35
 */
public class Code01RobotWalk {

    public static void main(String[] args) {
        //        System.out.println(robotWalk(7, 2, 4, 4));
        System.out.println(robotWalk2(4, 2, 4, 4));
        System.out.println(robotWalk3(4, 2, 4, 4));
    }

    static public int robotWalk3(int n, int start, int aim, int k) {
        int[][] cache = new int[n + 1][k + 1];
        cache[aim][0] = 1;
        for (int rest = 1; rest <= k; rest++) {
            cache[1][rest] = cache[2][rest - 1];
            for (int curPos = 2; curPos <= n - 1; curPos++) {
                cache[curPos][rest] = cache[curPos - 1][rest - 1] + cache[curPos + 1][rest - 1];
            }
            cache[n][rest] = cache[n - 1][rest - 1];
        }

        return cache[start][k];
    }

    static public int robotWalk2(int n, int start, int aim, int k) {

        int[][] cache = new int[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                cache[i][j] = -1;
            }
        }
        cache[aim][0] = 1;
        int res = process2(n, start, aim, k, cache);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                System.out.print(cache[i][j] + " , ");
            }
            System.out.println();
        }

        return cache[start][k];
        //        return res;
    }

    private static int process2(int n, int curPos, int aim, int rest, int[][] cache) {
        if (cache[curPos][rest] != -1) {
            return cache[curPos][rest];
        }

        if (rest == 0) {
            if (curPos == aim) {
                return 1;
            } else {
                return 0;
            }
        }

        if (curPos == 1) {
            cache[curPos][rest] = process2(n, curPos + 1, aim, rest - 1, cache);
            return cache[curPos][rest];
        }

        if (curPos == n) {
            cache[curPos][rest] = process2(n, curPos - 1, aim, rest - 1, cache);
            return cache[curPos][rest];
        }

        cache[curPos][rest] = process2(n, curPos + 1, aim, rest - 1, cache) + process2(n, curPos - 1, aim, rest - 1, cache);
        return cache[curPos][rest];
    }

    static public int robotWalk1(int n, int start, int aim, int k) {
        return process1(n, start, aim, k);
    }

    private static int process1(int n, int curPos, int aim, int k) {
        if (k == 0) {
            if (curPos == aim) {
                return 1;
            } else {
                return 0;
            }
        }

        if (curPos == 1) {
            return process1(n, curPos + 1, aim, k - 1);
        }

        if (curPos == n) {
            return process1(n, curPos - 1, aim, k - 1);
        }

        return process1(n, curPos + 1, aim, k - 1) + process1(n, curPos - 1, aim, k - 1);
    }

}
